/*
 * @lc app=leetcode.cn id=1365 lang=javascript
 *
 * [1365] 有多少小于当前数字的数字
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function (nums) {
  // 最大值
  let max_value = nums[0];
  // 最小值
  let min_value = nums[0];
  for (let num of nums) {
    if (num > max_value) {
      max_value = num;
    }
    if (num < min_value) {
      min_value = num;
    }
  }
  // 计算出差值，优化值域空间
  const diff = max_value - min_value;
  const count_array = new Array(diff + 1).fill(0);

  const size = nums.length;
  for (let i = 0; i < size; i++) {
    count_array[nums[i] - min_value]++;
  }

  const idxs_size = count_array.length;
  // 统计出前缀和
  for (let i = 1; i < idxs_size; i++) {
    count_array[i] += count_array[i - 1];
  }

  const result = [];
  for (let i = 0; i < size; i++) {
    result.push(nums[i] - min_value ? count_array[nums[i] - min_value - 1] : 0);
  }

  // 变化计数排序
  // const sort_array = new Array(size).fill(0);
  // for (let i = size - 1; i >= 0; i--) {
  //   sort_array[count_array[nums[i] - min_value] - 1] = nums[i];
  //   count_array[nums[i] - min_value]--;
  // }

  return result;
};
// @lc code=end

/**
 * 时间复杂度：O(N+K)，其中 K 为值域大小。需要遍历两次原数组，同时遍历一次频次数组 count_array 找出前缀和
 * 空间复杂度：O(K)。因为要额外开辟一个值域大小的数组
 */
